home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Language/OS - Multiplatform Resource Library
/
LANGUAGE OS.iso
/
cocktail
/
doc.lha
/
doc.doc
/
autogen.doc
< prev
next >
Wrap
Text File
|
1992-09-25
|
37KB
|
1,097 lines
___________________________________________________________________
Automatische Generierung
effizienter Compiler
J. Grosch
___________________________________________________________________
___________________________________________________________________
GESELLSCHAFT FUeR MATHEMATIK
UND DATENVERARBEITUNG MBH
FORSCHUNGSSTELLE FUeR
PROGRAMMSTRUKTUREN
AN DER UNIVERSITAeT KARLSRUHE
___________________________________________________________________
Project
Compiler Generation
___________________________________________________________
Automatische Generierung effizienter Compiler
Josef Grosch
Jan. 12, 1989
___________________________________________________________
Report No. 13
Copyright c 1989 GMD
Gesellschaft fuer Mathematik und Datenverarbeitung mbH
Forschungsstelle an der Universitaet Karlsruhe
Vincenz-Priesznitz-Str. 1
D-7500 Karlsruhe
1
Automatische Generierung effizienter Compiler
Josef Grosch
GMD Forschungsstelle fuer Programmstrukturen an der Universitaet Karlsruhe
Vincenz-Priesznitz-Str. 1, D-7500 Karlsruhe 1
Zusammenfassung
Das Projekt UWE (Uebersetzerbau-Werkzeuge) zielt auf die Erstellung von Gen-
eratorprogrammen, die es erlauben Compiler weitgehend automatisch zu erzeugen.
Fuer die Analysephase von Compilern werden drei Generatoren vorgestellt: Rex
ist ein Scanner-Generator auf der Basis regulaerer Ausdruecke. Der Parser-
Generator Lalr erzeugt aus LALR(1)-Grammatiken tabellengesteuerte Parser mit
S-Attributierung und automatischer Fehlerbehandlung. Der Parser-Generator Ell
erzeugt aus LL(1)-Grammatiken Parser nach dem Verfahren des rekursiven
Abstiegs mit einem Mechanismus zur L-Attributierung und ebenfalls automa-
tischer Fehlerbehandlung. Alle Generatoren sind in Modula-2 programmiert und
erzeugen Programme in C oder Modula-2. Die herausragende Eigenschaft der
erzeugten Programme ist ihre Geschwindigkeit. Auf einem MC 68020 Prozessor
erreichen die Scanner bis zu 200.000 und die Parser um die 400.000 Zeilen pro
Minute. Diese Geschwindigkeiten uebertreffen die UNIX Generatoren Lex und Yacc
um die Faktoren 4 bzw. 2 bis 3.
Abstract
The project UWE (compiler construction tools) has the goal to implement a com-
plete set of tools for the largely automatic construction of compilers. Three
tools for the analysis phase of compilers are presented: Rex is a scanner gen-
erator based on regular expressions. The parser generator Lalr generates
table-driven parsers for LALR(1) grammars that include a mechanism for S-
attribution and automatic error reporting, recovery, and repair. The parser
generator Ell generates recursive descent parsers for LL(1) grammars with a
mechanism for L-attribution and an automatic error recovery similar to Lalr.
All the tools are implemented in Modula-2 and generate programs in C or
Modula-2. The outstanding property of the generated programs is their speed.
On a MC 68020 processor the scanners reach up to 200,000 and the parsers
around 400,000 lines per minute. These speeds represent in comparison to the
UNIX tools Lex and Yacc a clear improvement by factors of 4 respectively 2 to
3.
Projekt-Ueberblick
Das Projekt UWE (fuer Uebersetzerbau-Werkzeuge) befaszt sich mit der
Technik des Uebersetzerbaus (Compiler-Baus), der Systematisierung der dabei
verwendeten Methoden und Verfahren sowie deren Umsetzung in Generatorpro-
gramme. Dies schlieszt die Entwicklung von Spezifikationstechniken fuer die
verschiedenen Compiler-Teile ein. Das Ziel ist die Erstellung eines vollstaen-
digen Satzes von Werkzeugen oder Generatorprogrammen zur weitgehend automa-
tischen Konstruktion von Compilern. Dabei wird gegenueber einer Compiler-Ent-
wicklung von Hand angestrebt, den Konstruktionsaufwand deutlich zu reduzieren,
2
die Fehlerfreiheit und Zuverlaessigkeit zu steigern und eine vergleichbare
Effizienz bzw. Uebersetzungsgeschwindigkeit zu erreichen.
Die Beschaeftigung mit Uebersetzerbau-Werkzeugen geht auf den Lehrstuhl
fuer Uebersetzerbau an der Universitaet Karlsruhe zurueck, aus dem heraus die
GMD Forschungsstelle Karlsruhe entstanden ist. Dort wurden bereits das Parser
Generating System PGS (LALR(1)-Zerteiler-Generator), der Generator fuer
Attribut-Grammatiken GAG (semantische Analyse) und das Code Generator Synthese
System CGSS (erzeugt Code-Generatoren aus Maschinenbeschreibungen) entwickelt.
Diese Werkzeuge wurden an der GMD Forschungsstelle Karlsruhe weiterentwickelt
und inzwischen weltweit an ueber 100 Institutionen weitergegeben. Diese quasi
erste Generation von Werkzeugen erfuellte bereits die Forderung nach
Steigerung der Zuverlaessigkeit der erzeugten Compiler-Teile. Das kann man am
erfolgreichen Einsatz fuer realistische Anwendungen sehen, wie etwa dem
Karlsruher Ada Compiler oder der Norm fuer PEARL. Die im folgenden vor-
gestellten Werkzeuge der zweiten Generation schlieszen die Luecke im Bereich
der lexikalischen Analyse und erzeugen fuer die Syntaxanalyse komfortable und
effiziente Zerteiler.
Der Scanner-Generator Rex
Der Scanner-Generator Rex wurde mit dem Ziel entwickelt, die maechtige
Spezifikationsmethode der regulaeren Ausdruecke mit der Generierung moeglichst
effizienter Scanner zu kombinieren. Der Name Rex steht fuer regular expression
tool und spiegelt die Spezifikationsmethode wider. Eine Scanner-Spezifikation
besteht im Prinzip aus einer Menge regulaerer Ausdruecke wobei jedem eine
semantische Aktion zugeordnet ist. Diese Aktionen sind beliebige Anweisungen,
die in einer der Zielsprachen C oder Modula-2 programmiert sind. Immer wenn
eine Zeichenkette, die durch einen regulaeren Ausdruck beschrieben wird, in
der Eingabe das Scanners erkannt wird, werden die Anweisungen der zugehoerigen
Aktion ausgefuehrt. Um Zeichenketten auch in Abhaengigkeit vom Kontext erken-
nen zu koennen stehen sogenannte Startzustaende zur Behandlung von linkem Kon-
text zur Verfuegung, und der rechte Kontext kann durch einen zusaetzlichen
regulaeren Ausdruck spezifiziert werden. Sollten mehrere regulaere Ausdruecke
zu einer Eingabe passen, so wird derjenige bevorzugt, der die laengste
Zeichenfolge erkennt. Falls immer noch mehrere Moeglichkeiten bestehen, wird
davon der erste regulaere Ausdruck in der Spezifikation gewaehlt.
Mit Rex erzeugte Scanner stellen automatisch fuer jede erkannte Zeichenk-
ette die Zeilen- und Spalten-Position zur Verfuegung. Fuer Sprachen wie Pascal
und Ada, wo Grosz- und Kleinbuchstaben nicht unterschieden werden, gibt es
eine Normalisierung auf Grosz- oder Kleinbuchstaben. Vordefinierte Regeln ges-
tatten das Ueberlesen unbedeutender Zeichen wie Leerzeichen, Tabulatoren oder
Zeilenwechsel.
Die erzeugten Scanner sind tabellengesteuerte deterministische endliche
Automaten. Da die Tabellen duenn besetzte Matrizen sind, werden sie mit der
sogenannten "Kammvektor-Technik" komprimiert. Diese kombiniert grosze
Speicherreduktion mit schnellem Tabellenzugriff. Der Generator Rex ist in
Modula-2 programmiert und kann zur Zeit Scanner in den Sprachen C und Modula-2
erzeugen. Rex laeuft inzwischen auf den Rechnern SUN/UNIX, PCS Cadmus/UNIX
und VAX/BSD UNIX bzw. ULTRIX.
3
Die herausragende Eigenschaft von Rex ist die Geschwindigkeit. Die
erzeugten Scanner verarbeiten bis zu 200.000 ohne und 150.000 Zeilen pro
Minute mit Anwendung eines Hash-Verfahrens fuer Bezeichner. Dies ist die vier-
fache Geschwindigkeit gegenueber Scannern, die mit dem UNIX-Werkzeug Lex
[Les75] erzeugt wurden. In typischen Faellen haben die generierten Scanner nur
ein Viertel der Groesze wie bei Lex (z. B. 11 KB fuer Modula-2). Gewoehnlich
benoetigt Rex nur 1/10 der Zeit von Lex um einen Scanner zu erzeugen. Die
genannten Zahlen wurden auf einem MC 68020 Prozessor gemessen.
Scanner-Spezifikation mit Rechts-Kontext
Die folgenden kleinen Beispiele zeigen wie Spezifikationen fuer Rex
[Gro87] aussehen. Abbildung 1 spezifiziert den Aufbau ganzer und reeller
Zahlen fuer die Sprache Modula-2. Die erste Zeile besagt, dasz eine ganze Zahl
aus Folgen von Zeichen aus der Menge 0 bis 9 besteht. In Modula-2 gibt es, wie
in manchen anderen Sprachen auch, eine Stelle, an der die Strategie der
laengsten Zeichenkette fehlschlaegt. So sollte etwa die Eingabe 1.. in die
Zeichenketten "1" und "..", nicht aber in "1." und "." zerlegt werden, was
alles legale Modula-2-Symbole waeren.
{0-9} + : { RETURN SymDecimal; }
{0-9} + / ".." : { RETURN SymDecimal; }
{0-9} + "." {0-9} * (E {+\-} ? {0-9} +) ?
: { RETURN SymReal ; }
".." : { RETURN SymRange ; }
"." : { RETURN SymDot ; }
Abbildung 1: Scanner-Spezifikation mit Rechts-Kontext
Das Problem kann mit einem zusaetzlichen regulaeren Ausdruck geloest wer-
den. Dieser beschreibt den rechten Kontext eines Symbols welches zu einer
Ausnahme der Strategie der laengsten Zeichenkette fuehrt. In der zweiten Zeile
trennt das Zeichen '/' zwei regulaere Ausdruecke und spezifiziert so, dasz
eine Ziffernfolge erkannt werden soll, wenn zwei Punkte folgen. Die restli-
chen Zeilen in Abbildung 1 beschreiben die weiteren Symbole, die an diesem
Problem beteiligt sind.
Scanner-Spezifikation mit Startzustaenden
Manche Probleme lassen sich mit regulaeren Ausdruecken allein nicht
loesen. So erfordert etwa die Erkennung geschachtelter Kommentare in Modula-2
einen zusaetzlichen Zaehler und den Einsatz von Startzustaenden (Abbildung 2).
Der Zaehler wird im Abschnitt GLOBAL deklariert und im Abschnitt BEGIN ini-
tialisiert. Der Abschnitt START vereinbart einen Startzustand namens Comment.
Regeln, vor denen ein Startzustand steht, sind nur wirksam, wenn sich der
Scanner in diesem Startzustand befindet. Die erste Regel erkennt oeffnende
Kommentarklammern, erhoeht den Schachtelungszaehler und schaltet in den Start-
zustand Comment um. In letzterem sind alle 3 Regeln wirksam. Entweder werden
Kommentarzeichen ueberlesen oder bei schlieszenden Kommentarklammern der
Schachtelungszaehler erniedrigt. Erreicht dieser den Wert Null, so ist der
Kommentar zu Ende, und es wird wieder in den vordefinierten Startzustand STD
4
GLOBAL {VAR NestingLevel: CARDINAL;}
BEGIN {NestingLevel := 0;}
EOF {IF yyStartState = Comment THEN Error ("unclosed comment"); END;}
DEFINE CmtCh = - {*(0.
START Comment
RULES
"(*" : {INC (NestingLevel); yyStart (Comment);}
#Comment# "*)" : {DEC (NestingLevel);
IF NestingLevel = 0 THEN yyStart (STD); END;}
#Comment# "(" | "*" | CmtCh + : {}
Abbildung 2: Scanner Spezifikation fuer geschachtelte Kommentare
zurueckgekehrt. Im Abschnitt EOF stehen Aktionen, die beim Erreichen des
Eingabeendes auszufuehren sind. Hier wird im Falle einer fehlenden Kommentark-
lammer ein entsprechender Fehler gemeldet.
Vergleich von Scanner-Generatoren
Die Tabelle 1 vergleicht Rex mit dem UNIX Scanner-Generator Lex und dem
Lex-Nachbau Flex (fuer fast Lex). Die Tabelle vergleicht die Spezifikation-
stechniken, die Werkzeuge und die generierten Scanner. Die spezifikations-
abhaengigen Zahlen wie Generierungszeit und Scanner-Groesze gelten fuer einen
Modula-2-Scanner. Die Zahlen wurden auf einem MC 68020 Prozessor gemessen.
Der Parser-Generator Lalr
Wie Rex wurde der Parser-Generator Lalr mit dem Ziel entwickelt eine mae-
chtige Spezifikationstechnik fuer kontextfreie Grammatiken mit der Erzeugung
effizienter Parser (Zerteiler) zu kombinieren. Der Name Lalr nimmt Bezug auf
die Klasse der LALR(1)-Grammatiken, fuer die Zerteiler erzeugt werden koennen.
Diese Grammatiken koennen in erweiterter BNF geschrieben sein. Jede Gramma-
tikregel kann mit semantischen Aktionen versehen werden, welche wiederum aus
beliebigen Anweisungen der Zielsprache bestehen. Wenn der erzeugte Zerteiler
eine Grammatikregel erkannt hat, werden die zugeordneten Aktionen ausgefuehrt.
Es steht ein Mechanismus zur S-Attributierung zur Verfuegung, d. h.
abgeleitete Attribute koennen waehrend der Zerteilung berechnet werden.
Gehoert eine Grammatik nicht zur LALR(1)-Klasse, so stellt der Generator
LR-Konflikte fest. Das Problem dabei besteht darin, fuer einen Konflikt aus-
sagekraeftige Information zu liefern, um das Problem in der Grammatik finden
zu koennen und dann fuer Abhilfe zu sorgen. Waehrend andere Generatoren meist
nur den Konflikt in Begriffen von internen Zustaenden und Situationen melden
gibt Lalr Ableitungsbaeume aus, die die Konfliktbehebung wesentlich
erleichtern. Syntaxfehler werden von den generierten Zerteilern vollautoma-
tisch behandelt. Dies schlieszt Fehlermeldung, Wiederaufsetzen der Analyse und
Fehlerreparatur ein. (Die genannten Eigenschaften werden unten naeher aus-
gefuehrt.)
5
Tabelle 1: Vergleich einiger Scanner-Generatoren
____________________________________________________________________________________________
Lex Flex Rex
____________________________________________________________________________________________
Spezifikationsmethode regulaere regulaere regulaere
Ausdruecke Ausdruecke Ausdruecke
semantische Aktionen ja ja ja
Rechts-Kontext ja ja ja
Links-Kontext (Startzustaende) ja ja ja
____________________________________________________________________________________________
Konfliktloesung laengste Folge laengste Folge laengste Folge
erste Regel erste Regel erste Regel
____________________________________________________________________________________________
Quellposition Zeile - Zeile + Spalte
Normalisierung - ja ja
vordefinierte Regeln zum - - ja
Ueberlesen
mehrere Loesungen (REJECT) ja ja -
Anpassung interner von Hand automatisch automatisch
Datenstrukturen
____________________________________________________________________________________________
Scanneralgorithmus tabellengesteuert tabellengesteuert tabellengesteuert
Tabellenkompression Kammvektor Kammvektor Kammvektor
____________________________________________________________________________________________
Implementierungssprache C C Modula-2
Zielsprachen C C C, Modula-2
____________________________________________________________________________________________
Geschwindigkeit [Zeilen/Min.]
ohne Hashing 36.400 139.000 182.700
mit Hashing 34.700 118.000 141.400
____________________________________________________________________________________________
Tabellengroesze [Bytes] 39.200 57.300 4.400
Scanner-Groesze [Bytes] 43.800 64.100 11.200
____________________________________________________________________________________________
Generierungszeit [Sek.] 73,7 7,2 4,9
____________________________________________________________________________________________
Die erzeugten Parser sind tabellengesteuert, wobei die Tabellen wie im
Fall von Rex mittels Kammvektor-Technik komprimiert werden. Der Generator Lalr
ist in Modula-2 programmiert und kann zur Zeit Zerteiler in C und Modula-2
erzeugen. Wie Rex laeuft Lalr inzwischen auf den Rechnern SUN/UNIX, PCS
Cadmus/UNIX und VAX/BSD UNIX bzw. ULTRIX.
Mit Lalr erzeugte Zerteiler sind 2 bis 3 Mal schneller als mit dem UNIX
Werkzeug Yacc [Joh75] generierte. Sie erreichen eine Geschwindigkeit von bis
zu 400.000 Zeilen pro Minute auf einem MC 68020 Prozessor, wobei die Zeit fuer
den Scanner nicht beruecksichtigt ist. Von der Groesze her sind die Zerteiler
im Vergleich zu Yacc etwas groeszer (z. B. 37 KB fuer Ada). Im folgenden wer-
den einige Eigenschaften von Lalr naeher vorgestellt.
S-Attributierung
Die Spezifikation eines Zerteilers [GrV88] folgt dem Stil einer Rex Spez-
ifikation. Abbildung 3 zeigt ein einfaches Beispiel fuer einen Tischrechner,
6
welcher arithmetische Ausdruecke akzeptiert, die aus den Operatoren + und *
sowie Klammern und Zahlen aufgebaut sind. Die in den geschweiften Klammern
stehenden semantischen Aktionen sorgen fuer die Berechnung der Ausdruecke.
Dazu wird dem Nichtterminal expr und dem Terminal number das Attribut value
zugeordnet. Mit $i wird in den semantischen Aktionen auf die Attribute
zugegriffen. Dabei bedeuten $i das i-te Grammatiksymbol der rechten Seite und
$$ das Nichtterminal der linken Seite einer Regel.
expr : expr '+' expr { $$.value := $1.value + $3.value; } .
expr : expr '*' expr { $$.value := $1.value * $3.value; } .
expr : '(' expr ')' { $$.value := $2.value; } .
expr : number { $$.value := $1.value; } .
Abbildung 3: Grammatikregeln mit S-Attributierung
Mehrdeutige Grammatiken
Die Grammatik in Abbildung 3 und die Regeln in Abbildung 4 sind typische
Beispiele fuer mehrdeutige Grammatiken. Wie bei Yacc lassen sich daraus resul-
tierende LR-Konflikte durch die Angabe von Prioritaet und Assoziativitaet fuer
Terminale (Operatoren) loesen. Abbildung 5 zeigt ein Beispiel. Die Zeilen
stellen zunehmende Prioritaeten dar. LEFT, RIGHT und NONE spezifizieren
links-assoziative, rechts-assoziative bzw. Operatoren ohne Assoziativitaet.
stmt : 'IF' expr 'THEN' stmt PREC LOW
| 'IF' expr 'THEN' stmt 'ELSE' stmt PREC HIGH .
Abbildung 4: Mehrdeutige Grammatikregeln (Dangling Else Problem von Pascal)
OPER LEFT '+'
LEFT '*'
NONE LOW
NONE HIGH
Abbildung 5: Loesen von LR-Konflikten mit Prioritaet und Assoziativitaet
Beschreibung von LR-Konflikten
Zur leichteren Lokalisierung des Grundes fuer LR-Konflikte wurde eine von
DeRemer und Pennello [DeP82] vorgeschlagene Methode aufgegriffen. Neben der
Art des Konflikts und den beteiligten Situationen wie bei anderen LR-
Generatoren wird zusaetzlich ein Ableitungsbaum ausgegeben. Eine Situation
(item) ist eine Grammatikregel mit einem zusaetzlichen Punkt in der rechten
Seite, welcher angibt, wie weit diese Regel bereits analysiert wurde. Abbil-
dung 6 zeigt ein Beispiel.
Der Baum zeigt wie die Situationen und die Vorschauzeichen in den Kon-
fliktzustand gelangen. Im allgemeinen wird fuer jede beteiligte Situation ein
eigener Baum ausgegeben. Sind die Baeume jedoch gleich, wie das in Abbildung 6
7
State 266
read reduce conflict
program End-of-Tokens
'PROGRAM' identifier params ';' block '.'
................................:
:
labels consts types vars procs 'BEGIN' stmts 'END'
.......................................:
:
stmt
'IF' expr 'THEN' stmt 'ELSE' stmt
:
reduce stmt -> 'IF' expr 'THEN' stmt. {'ELSE'} ?
read stmt -> 'IF' expr 'THEN' stmt.'ELSE' stmt ?
Abbildung 6: Ableitungsbaum fuer einen LR-Konflikt (Dangling Else Problem)
der Fall ist, so wird nur ein Baum ausgegeben. Jeder Baum besteht aus drei
Teilen: Ein Anfangsteil beginnt mit dem Startsymbol. An einem bestimmten
Knoten (Regel) erklaeren zwei weitere Teilbaeume die Entstehung der Situation
und der Vorschau.
Jede Zeile enthaelt die rechte Seite einer Grammatikregel. Normalerweise
ist diese rechte Seite so eingerueckt, dasz sie unter dem Nichtterminal der
linken Seite beginnt. Um zu lange Zeilen zu vermeiden, verweisen punktierte
Linienzuege ebenfalls zum Nichtterminal der linken Seite und erlauben so am
linken Rand fortzufahren. In Abbildung 6 besteht der Anfangsteil des Baumes
aus 5 Zeilen, wobei die punktierten Zeilen nicht gezaehlt wurden. Die Symbole
'stmt' und 'ELSE' sind die Wurzeln der beiden weiteren Teilbaeume. Diese
Stelle ist mit einem "ueberfluessigen" Doppelpunkt gekennzeichnet. Nach einem
Ableitungsschritt werden im linken Teilbaum die Konfliktsituationen erreicht.
Der rechte Teilbaum besteht in diesem Fall nur aus dem Wurzelknoten (dem Sym-
bol 'ELSE') und beschreibt das Vorschauzeichen. Im allgemeinen kann hier ein
Baum von beliebiger Groesze stehen. Der LR-Konflikt kann in diesem Baumfrag-
ment leicht abgelesen werden. Falls bedingte Anweisungen wie gezeigt
geschachtelt werden liegt ein Lies-Reduziere-Konflikt vor.
Fehlerbehandlung
Die generierten Zerteiler enthalten Information und Algorithmen um Syn-
taxfehler vollautomatisch zu behandeln. Es wird die vollstaendige, rueckset-
zungsfreie Methode von Roehrich [Roeh76,Roeh80,Roeh82] verwendet. Diese
schlieszt Fehlermeldungen, Wiederaufsetzen und Fehlerreparatur ein. Jede syn-
taktisch fehlerhafte Eingabe wird gedachterweise in ein korrektes Programm
transformiert. Dies bewirkt, dasz nur korrekte Folgen von semantischen
Aktionen ausgefuehrt werden. Dadurch brauchen spaetere Compiler-Phasen wie die
semantische Analyse auf Syntaxfehler keine Ruecksicht nehmen. Lalr stellt
einen Modul zur Sammlung oder Meldung von Fehlern zur Verfuegung, der leicht
an Benutzerwuensche anpaszbar ist. Ohne Modifikation werden Fehlermeldungen
wie in Abbildung 7 ausgegeben. Die Fehlerbehandlung laeuft in folgenden
Schritten ab:
8
Quellprogramm:
program test (output);
begin
if (a = b] write (a);
end.
Fehlermeldungen:
3, 13: Error syntax error
3, 13: Information expected symbols: ')' '*' '+' '-' '/' '<' '<='
'=' '<>' '>' '>=' 'AND' 'DIV' 'IN' 'MOD' 'OR'
3, 15: Information restart point
3, 15: Repair symbol inserted : ')'
3, 15: Repair symbol inserted : 'THEN'
Abbildung 7: Beispiel einer automatischen Fehlerbehandlung
- Die Position des Syntaxfehlers wird gemeldet.
- Alle Terminale, die eine korrekte Fortsetzung des Programms waeren, werden
berechnet und gemeldet.
- Alle Terminale, die zum Wiederaufsetzen der Zerteilung geeignet sind, werden
berechnet. Eine minimale Folge von Terminalen wird ueberlesen, bis eines
dieser Symbole gefunden wird.
- Die Position des Wiederaufsetzens wird gemeldet.
- Die Zerteilung wird im sogenannten Reparaturmodus fortgesetzt. In diesem
Modus verhaelt sich der Zerteiler wie gewohnt ohne jedoch Terminale von der
Eingabe zu lesen. Stattdessen wird eine minimale Folge von Terminalen gen-
eriert, die gedachterweise die ueberlesenen Terminale ersetzt. Diese generi-
erten Terminale werden gemeldet. Der Zerteiler bleibt in diesem Modus, bis
das Terminal am Aufsetzpunkt akzeptiert werden kann. Danach wird der Repara-
turmodus verlassen und die Zerteilung normal fortgesetzt.
Der Parser-Generator Ell
Der Parser-Generator Ell erzeugt aus LL(1)-Grammatiken Zerteiler nach dem
Verfahren des rekursiven Abstiegs. Die Grammatiken koennen in erweiterter BNF
geschrieben sein und semantische Aktionen enthalten. Innerhalb der Aktionen
ist es moeglich eine L-Attribut-Berechnung zu spezifizieren, die waehrend der
Zerteilung ausgewertet wird. Es koennen sowohl erworbene als auch abgeleitete
Attribute benutzt werden, solange die Auswertung in einem Links-Rechts-
Durchlauf des Ableitungsbaums moeglich ist. Syntaxfehler werden wie bei Lalr
vollautomatisch behandelt mit Fehlermeldungen, Wiederaufsetzen und Fehler-
reparatur. Das Werkzeug ist ebenfalls in Modula-2 programmiert und kann Zer-
teiler in C und Modula-2 erzeugen. Die Geschwindigkeit der erzeugten Zerteiler
liegt im Augenblick bei 450.000 Zeilen pro Minute. Zur Zeit wird an einigen
Verbesserungen gearbeitet, wodurch dieser Wert noch steigen wird. Der
Speicherbedarf liegt in der Groeszenordnung von tabellengesteuerten Zerteilern
(z. B. 14 KB fuer Modula-2).
9
ExpList : ( Expr ';' { Write (Expr1.value, 10); }
) *
.
Expr : ( ['+'] Term { Expr0.value := Term1.value; }
| '-' Term { Expr0.value := - Term2.value; }
)
( '+' Term { INC (Expr0.value, Term3.value); }
| '-' Term { DEC (Expr0.value, Term4.value); }
) *
.
Term : Factor { Term0.value := Factor1.value; }
( '*' Factor { Term0.value := Term0.value * Factor2.value; }
| '/' Factor { Term0.value := Term0.value DIV Factor3.value; }
) *
.
Factor : Number { Factor0.value := Number1; }
| '(' Expr ')' { Factor0.value := Expr1.value; }
.
Abbildung 8: LL(1)-Grammatik fuer einfachen Tischrechner
Abbildung 8 zeigt die Spezifikation eines einfachen Tischrechners mit 4
Grundrechenarten fuer Ell. Die Spezifikation erfolgt durch eine LL(1)-
Grammatik in erweiterter BNF. Die in geschweifte Klammern eingeschlossenen
semantischen Aktionen berechnen wiederum den Wert eines eingegebenen Ausdrucks
und geben ihn aus. Der Zugriff auf Attribute erfolgt hier ueber die Namen der
Grammatiksymbole. Da mehrere gleichnamige Symbole in einer Regel vorkommen
koennen werden zur Unterscheidung an die Namen Zahlen angehaengt. Die Zahl 0
bezeichnet das Nichtterminal der linken Seite. Mit Zahlen groeszer 0 werden
gleichnamige Symbole der rechten Seite von links nach rechts durchgezaehlt.
Vergleich von Parser-Generatoren
Abschlieszend vergleicht die Tabelle 2 die Parser-Generatoren Lalr und
Ell mit dem UNIX Werkzeug Yacc, mit dem Yacc-Nachbau Bison und mit PGS (siehe
oben). Die Tabelle faszt die angesprochenen Eigenschaften zusammen und sollte
selbsterklaerend sein. Die sprachabhaengigen Zahlen sind ohne Laufzeit und
Speicherbedarf fuer Scanner und beziehen sich auf Experimente mit einem Parser
fuer Modula-2.
Zusammenfassung
Die Uebersetzerbau-Werkzeuge Rex, Lalr und Ell wurden mit dem Ziel
entworfen, maechtige Spezifikationstechniken mit der automatischen Erzeugung
effizienter Compiler-Teile zu kombinieren. Es koennen Scanner und Parser in C
und Modula-2 erzeugt werden, die sich vor allem durch ihre Geschwindigkeit
auszeichnen. Die Scanner verarbeiten bis zu 200.000 und die Parser etwa
400.000 Zeile pro Minute auf einem MC 68020 Prozessor. Zusammen erreichen
Scanner und Parser mehr als 100.000 Zeilen pro Minute oder fast 2000 Zeilen
pro Sekunde.
10
Tabelle 2: Vergleich einiger Parser-Generatoren
___________________________________________________________________________________________________
Bison Yacc PGS Lalr Ell
___________________________________________________________________________________________________
Spezifikationsmethode BNF BNF EBNF EBNF EBNF
Grammatikklasse LALR(1) LALR(1) LALR(1) LALR(1) LL(1)
LR(1)
SLR(1)
semantische Aktionen ja ja ja ja ja
S-Attributierung numerisch numerisch symbolisch numerisch -
L-Attributierung - - - - symbolisch
___________________________________________________________________________________________________
Konfliktmeldung Zustand, Zustand, Zustand, Ableitungs- -
Situation Situation Situation baum
Konfliktloesung Prioritaet Prioritaet Modifikation Prioritaet
Assoziativitaet Assoziativitaet Assoziativitaet
Kettenregelelimination - - ja - -
Fehlerbehandlung von Hand von Hand automatisch automatisch automatisch
Fehlerreparatur - - ja ja ja
___________________________________________________________________________________________________
Zerteilungsverfahren tabellen- tabellen- tabellen- tabellen- rekursiver
gesteuert gesteuert gesteuert gesteuert Abstieg
Tabellenkompression Kammvektor Kammvektor Kammvektor Kammvektor -
___________________________________________________________________________________________________
Implementgs.-Sprache C C Pascal Modula-2 Modula-2
Zielsprachen C C C C C
Modula-2 Modula-2 Modula-2
Pascal
Ada
___________________________________________________________________________________________________
Geschwindigkeit 105.000 184.000 200.000 385.000 437.000
[Zeilen/Min.]
___________________________________________________________________________________________________
Tabellengroesze [Bytes] 8.004 10.364 11.268 11.795 -
Zerteilergroesze [Bytes] 11.136 12.548 17.616 17.416 14.344
___________________________________________________________________________________________________
Generierungszeit [Sek.] 5,0 19,6 69,5 29,6 6,4
___________________________________________________________________________________________________
Da erfahrungsgemaesz der Scanner einen Groszteil der gesamten Ueberset-
zungszeit verbraucht, hoffen wir vollstaendige Compiler mit einer Geschwindig-
keit von 1000 Zeilen pro Sekunde automatisch erzeugen zu koennen. Im Augen-
blick wird an der Vervollstaendigung des Werkzeugsatzes gearbeitet. Dies
betrifft Werkzeuge fuer die semantische Analyse auf der Basis attributierter
Grammatiken, Werkzeuge fuer die Transformation wie etwa die Erzeugung einer
Zwischensprache und Werkzeuge fuer die Codeerzeugung auf der Basis von Muster-
abgleich (pattern matching).
Der Generator Lalr wurde von Bertram Vielsack programmiert, der auch die
experimentellen Ergebnisse fuer den Vergleich der Parser-Generatoren beitrug.
Der Generator Ell wurde von Doris Kuske programmiert.
11
Literatur
[DeP82]
F. DeRemer and T. Pennello, Efficient Computation of LALR(1) Look-Ahead
Sets, ACM Trans. Prog. Lang. and Systems 4, 4 (Oct. 1982), 615-649.
[Gro87]
J. Grosch, Rex - A Scanner Generator, Compiler Generation Report No. 5,
GMD Forschungsstelle an der Universitat Karlsruhe, Dec. 1987.
[GrV88]
J. Grosch and B. Vielsack, The Parser Generators Lalr and Ell, Compiler
Generation Report No. 8, GMD Forschungsstelle an der Universitat
Karlsruhe, Apr. 1988.
[Joh75]
S. C. Johnson, Yacc - Yet Another Compiler-Compiler, Computer Science
Technical Report 32, Bell Telephone Laboratories, Murray Hill, NJ, July
1975.
[Les75]
M. E. Lesk, LEX - A Lexical Analyzer Generator, Computing Science
Technical Report 39, Bell Telephone Laboratories, Murray Hill, NJ, 1975.
[Roeh76]
J. Rohrich, Syntax-Error Recovery in LR-Parsers, in Informatik-
Fachberichte, vol. 1, H.-J. Schneider and M. Nagl (ed.), Springer Verlag,
Berlin, 1976, 175-184.
[Roeh80]
J. Rohrich, Methods for the Automatic Construction of Error Correcting
Parsers, Acta Inf. 13, 2 (1980), 115-139.
[Roeh82]
J. Rohrich, Behandlung syntaktischer Fehler, Informatik Spektrum 5, 3
(1982), 171-184.
Inhalt
Zusammenfassung ................................................. 1
Abstract ........................................................ 1
Projekt-Ueberblick .............................................. 1
Der Scanner-Generator Rex ....................................... 2
Scanner-Spezifikation mit Rechts-Kontext ........................ 3
Scanner-Spezifikation mit Startzustaenden ....................... 3
Vergleich von Scanner-Generatoren ............................... 4
Der Parser-Generator Lalr ....................................... 4
S-Attributierung ................................................ 5
Mehrdeutige Grammatiken ......................................... 6
Beschreibung von LR-Konflikten .................................. 6
Fehlerbehandlung ................................................ 7
Der Parser-Generator Ell ........................................ 8
Vergleich von Parser-Generatoren ................................ 9
Zusammenfassung ................................................. 9
Literatur ....................................................... 11